/*
 *  An indexed max priority queue
 */
package algs4.ds;

import java.util.Random;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class IndexMaxPQ<Key extends Comparable<Key>> implements Iterable<Integer>, Cloneable
{
    /* Inner Class */
    private class HeapIterator implements Iterator<Integer>
    {
        private IndexMaxPQ<Key> cp;

        public HeapIterator() {
            try {
                cp = IndexMaxPQ.this.clone();
            } catch (CloneNotSupportedException e) {
                e.printStackTrace();
            }
         }

        public boolean hasNext() { return !cp.isEmpty(); }
        public Integer next()    { return cp.delMax();   }
    }

    /* Fields */
    private int[] pq;   // index priority queue
    private int[] qp;   // inverse of pq, qp[pq[i]] = pq[qp[i]] = i
    private Key[] keys; // corresponding keys
    private int   sz;   // size of priority queue
    private int   maxSize;

    /* Constructors */
    public IndexMaxPQ(int maxN) {
        pq      = new int[maxN + 1];
        qp      = new int[maxN + 1];    // make this of length maxN?
        keys    = (Key[]) new Comparable[maxN];
        sz      = 0;
        maxSize = maxN;

        for (int i = 0; i < maxN; i++) qp[i] = -1;
    }

    /* Instance Methods */
    public boolean           isEmpty()  { return sz == 0;            }
    public int               size()     { return sz;                 }
    public Iterator<Integer> iterator() { return new HeapIterator(); }

    public IndexMaxPQ<Key> clone() throws CloneNotSupportedException {
        IndexMaxPQ<Key> cloned = new IndexMaxPQ<>(maxSize);

        cloned.sz = sz;

        System.arraycopy(pq, 1, cloned.pq, 1, sz);
        System.arraycopy(qp, 0, cloned.qp, 0, maxSize);
        System.arraycopy(keys, 0, cloned.keys, 0, maxSize);

        return cloned;
    }

    public boolean contains(int i) {
        // check whether i is valid
        if (i < 0 || i >= maxSize)
            throw new IllegalArgumentException("Index out of bounds");

        return qp[i] != -1;
    }

    public void insert(int i, Key key) {
        // check whether i is valid
        if (i < 0 || i >= maxSize)
            throw new IllegalArgumentException("Index out of bounds");
        if (contains(i))
            throw new IllegalArgumentException("index is alread in PQ");

        // update
        pq[++sz] = i;
        qp[i]    = sz;
        keys[i]  = key;
        swim(sz);
    }

    public void change(int i, Key key) {
        // check whether i is valid
        if (i < 0 || i >= maxSize)
            throw new IllegalArgumentException("Index out of bounds");
        if (!contains(i))
            throw new NoSuchElementException("Index is not in PQ");

        // update
        keys[i] = key;

        int k = qp[i];  // position of element i

        swim(k);
        sink(k);
    }

    public void delete(int i) {
        int k = qp[i];  // position of element i

        // put last element to position k
        pq[k]     = pq[sz--];
        qp[pq[k]] = k;

        swim(k);
        sink(k);

        // delete element i
        qp[i]   = -1;
        keys[i] = null;
    }

    public int delMax() {
        // check whether PQ is empty
        if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");

        // retrieve element
        int i = pq[1];

        // put last element to root of binary heap
        pq[1]     = pq[sz--];
        qp[pq[1]] = 1;

        sink(1);

        // delete element i
        qp[i]     = -1;
        keys[i]   = null;

        return i;
    }

    public int max() {
        // check whether PQ is empty
        if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");

        return pq[1];
    }

    public Key maxKey() {
        // check whether PQ is empty
        if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");

        return keys[pq[1]];
    }

    /* Private Instance Methods */
    private void swim(int k) {
        int v = pq[k];

        while (k > 1 && keys[v].compareTo(keys[pq[k / 2]]) > 0) {
            pq[k]     = pq[k / 2];
            qp[pq[k]] = k;
            k /= 2;
        }

        pq[k] = v;
        qp[v] = k;
    }

    private void sink(int k) {
        int v = pq[k];

        int i;
        while ((i = 2 * k) <= sz) {
            if (i < sz && keys[pq[i]].compareTo(keys[pq[i + 1]]) < 0) i++;

            if (keys[v].compareTo(keys[pq[i]]) < 0) {
                pq[k]     = pq[i];
                qp[pq[k]] = k;
                k         = i;
            } else {
                break;
            }
        }

        pq[k] = v;
        qp[v] = k;
    }

    /* Main Test */
    public static void main(String[] args) {
        Integer[] a = new Integer[25];
        Random    r = new Random(System.currentTimeMillis());

        for (int i = 0; i < 25; i++) a[i] = r.nextInt(100);

        // show data
        System.out.println("Before: ");

        System.out.print("i: ");
        for (int i = 0; i < 25; i++) System.out.printf("%2d ", i);
        System.out.println();

        System.out.print("n: ");
        for (int i = 0; i < 25; i++) System.out.printf("%2d ", a[i]);
        System.out.println();

        // create Priority Queue
        IndexMaxPQ<Integer> ipq = new IndexMaxPQ<>(25);

        // insert elements
        for (int i = 0; i < 25; i++) ipq.insert(i, a[i]);

        // change elements
        ipq.change(5, 0);
        ipq.change(10, 25);
        ipq.delete(15);
        ipq.change(20, 99);

        // show data
        System.out.println("After: ");

        System.out.print("i: ");
        for (Integer i : ipq) System.out.printf("%2d ", i);
        System.out.println();

        System.out.print("n: ");
        while (!ipq.isEmpty()) { System.out.printf("%2d ", ipq.maxKey()); ipq.delMax(); };
        System.out.println();
    }
}
